package demo12;

import java.util.Arrays;

public class Solution {
//
//    //1.买卖股票的最佳时机(动态规划)
//    public int maxProfit(int[] prices) {
//        int[][] dp = new int[prices.length][2];
//        //初始化
//        dp[0][0] = -prices[0];//持有这个股票
//        dp[0][1] = 0;//不持有这个股票
//        for(int i = 1; i < prices.length; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
//        }
//        return dp[prices.length - 1][1];
//    }

    //2.买卖股票的最佳时机II(动态规划)
//    public int maxProfit(int[] prices) {
//        int[][] dp = new int[prices.length][2];
//        dp[0][0] = -prices[0];//持有
//        dp[0][1] = 0;//不持有
//        for(int i = 1; i < prices.length; i++) {
//            //第i天持有股票
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//            //第i天不持有股票
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
//        }
//        return dp[prices.length - 1][1];
//    }
//
//    //3.买卖股票的最佳时机 III(动态规划)
//    public int maxProfit(int[] prices) {
//        int[][] dp = new int[prices.length][5];
//        //初始化
//        dp[0][0] = 0;//不操作
//        dp[0][1] = -prices[0];//第一次持有
//        dp[0][2] = 0;//第一次不持有
//        dp[0][3] = -prices[0];//第二次持有
//        dp[0][4] = 0;//第二次不持有
//        for(int i = 1; i < prices.length; i++) {
//            dp[i][0] = dp[i - 1][0];
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
//        }
//        return dp[prices.length - 1][4];
//    }

//
//    //4.买卖股票的最佳时机 IV(动态规划)
//    public int maxProfit(int k, int[] prices) {
//        int ans = 2 * k + 1;
//        int[][] dp = new int[prices.length][ans];
//        //初始化
//        for(int i = 0; i < ans; i++) {
//            dp[0][i] = i % 2 == 0 ? 0 : -prices[0];
//        }
//        //遍历
//        for(int i = 1; i < prices.length; i++) {
//            dp[i][0] = dp[i - 1][0];
//            for(int j = 1; j < ans; j++) {
//                if(j % 2 == 1) { //买入
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
//                } else {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
//                }
//            }
//        }
//        return dp[prices.length - 1][ans - 1];
//    }
//
//    //5.最佳买卖股票时机含冷冻期(动态规划)
//    public int maxProfit(int[] prices) {
//        int len = prices.length;
//        int[][] dp = new int[len][4];
//        dp[0][0] = -prices[0];//持股
//        dp[0][1] = 0;//冷冻期后的不持股
//        dp[0][2] = 0;//当天卖出股票
//        dp[0][3] = 0;//冷冻期
//        for(int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
//            dp[i][2] = dp[i - 1][0] + prices[i];
//            dp[i][3] = dp[i - 1][2];
//        }
//        return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
//    }

    //6.买卖股票的最佳时机含手续费(动态规划)
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];//持股
        dp[0][1] = 0;//不持股
        for(int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[prices.length - 1][1];
    }

    //7.最长递增子序列(动态规划)
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        //初始化
        Arrays.fill(dp, 1);//以某一值为结尾，那么长度至少是1
        int result = 1;//保存结果
        //递推
        for(int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {//注意是递增
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            result = Math.max(dp[i], result);
        }
        return result;
    }
//
//    //8.最长连续递增序列
//    public int findLengthOfLCIS(int[] nums) {
//        int[] dp = new int[nums.length];
//        Arrays.fill(dp, 1);
//        int result = 0;
//        for(int i = 0; i < nums.length; i++) {
//            for(int j = 0; j < i; j++) {
//                if(j + 1 == i && nums[j] < nums[i]) {
//                    dp[i] = Math.max(dp[i], dp[j] + 1);
//                }
//            }
//            result = Math.max(result, dp[i]);
//        }
//        return result;
//    }

    //优化
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 1;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i - 1] < nums[i]) {
                dp[i] = dp[i - 1] + 1;
            }
            if(dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }

    //9.最长重复子数组(动态规划)
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++) {
            for(int j = 1; j <= nums2.length; j++) {
                if(nums1[i - 1] == nums2[j - 1]) { //注意定义
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if(result < dp[i][j]) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }

    //10.最长公共子序列(动态规划)
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        int result = 0;
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                if(dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }

}

class Main {
    public static void main(String[] args) {
        int[] arr1 = {1,2,3,9,2,1};
        int[] arr2 = {3,8,2,1,4,7};
        Solution solution = new Solution();
        solution.findLength(arr1, arr2);
    }
}
